1. Field of the Invention
The present invention generally relates to address allocation in wireless multi-hop network and, more particularly, to a prime numbering address allocation method and a unique numbering address allocation method using the same in wireless multi-hop network.
2. Description of the Related Art
A wireless multi-hop network usually is a wireless network without the support of base stations, such as a mobile ad-hoc network (MANET), sensor network, and wireless mesh network (WMN). Without base stations, wireless networks provide high flexibility but have a limitation of applying existing communication methods designed for infrastructure directly, for example, the address allocation in a wireless multi-hop network is more complicated to maintain efficiency and uniqueness.
Traditionally, a host can configure its address statically or dynamically. In the static configuration, users need to acquire an available address in advance and manually configure the address. However, it is not reasonable for users to do manual configuration in a flexible multi-hop network. The other choice is dynamic configuration, which allows a host to configure an address dynamically, such as Dynamic Host Configuration Protocol (DHCP).
DHCP is a centralized allocation mechanism, which deploys at least one fixed server to manage all addresses in the network. FIG. 1 shows the message flows of DHCP. As shown, there are two DHCP servers 11, 12 and one DHCP relay 13 for DHCP server 12. When a new host 14 joins a multi-hop wireless network, it broadcasts a DHCP_Discover message to ask for an address. All hosts in the network except DHCP relay 13 will help rebroadcast such message until to DHCP servers 11, 12, whereas DHCP relay 13 will unicast the message to the DHCP server 12 directly. Upon receiving DHCP_Discover message, each of the DHCP servers 11, 12 will allocate an address and send DHCP_Offer message with the address back to the new host 14. Therefore, the new host 14 might receive multiple DHCP_Offer messages, and it has to choose one and broadcasts DHCP_Request to inform all servers 11, 12 its choice, for example server 12. The chosen server 12 will check if such address is really available and send DHCP_Ack to the new host 14. At this time, the new host 14 can configure the address as its address and start the process of DAD (Duplicate Address Detection) to guarantee that no other hosts in the network use such an address. After a lease time, which is assigned by the server 12 notifying how long the host 14 can use such address, the host 14 reclaims the address by DHCP_Request. If the address is still available, the server 12 will send a DHCP_Ack message to the host 14. Otherwise, a DHCP_Nack message will be sent and the host 14 needs to perform the whole procedure starting from broadcasting DHCP_Discover again.
In view of the message flows of DHCP, it is known that, in dynamic configurations, broadcasts are usually necessary to acquire an address or detect address confliction. However, broadcast in a wireless multi-hop network is very expensive and may cause broadcast storm problem.
In the known address allocation mechanisms, self-configuration is a distributed address allocation mechanism, in which a host can configure its address by itself according to different factors, such as its hardware address (S. Cheshire, B. Aboba, and E. Guttman, Dynamic Configuration of IPv4 Link-Local Addresses, draft-ietf.zeroconf-ipv4-linklocal-17.txt, IETF Zeroconf Working Group, July 2004; S. Thomson and T. Narten, IPv6 Stateless Address Autoconfiguration, RFC 2462, December 1998) or a random number (C. E. Perkins, J. T. Malinen, R. Wakikawa, E. M. Belding-Royer, and Y. Sun, IP Address Autoconfiguration for Ad Hoc Networks, draft-ietfmanet-autoconf-01.txt, IETF MANET Working Group, July 2000). Since a self-configured address is generated by an individual host, the address has to be checked by DAD to confirm that it is not occupied by other hosts. Therefore, broadcasts are still necessary to detect address confliction.
MANETconf (S. Nesargi, and R. Prakash, MANETconf: Configuration of Hosts in a Mobile Ad Hoc Network, INFOCOM 2002) is also a distributed method of address allocation in MANET by making all hosts record used addresses, wherein a new host acquires an address from one of its neighbors, and the neighbor finds an address not existing in its record and asks for confirmation by all other hosts in the MANET. If the address is not used by any other host, it will be assigned to the new coming host. In MANETconf, since confirmations are required from all other hosts, broadcasts are still required.
Prophet address allocation (H. Zhou, L. M. Ni, and M. W. Mutka, Prophet address allocation for large scale MANETs, INFOCOM 2003) tries to find a function which can generate a unique sequence of addresses for each host to be assigned in order. As a result, each host can directly assign addresses in the order of its address sequence without asking other hosts. However, it is quite complex to maintain uniqueness between sequences, and the uniqueness is almost impossible while the address space is small. As a result, prophet address allocation is limited in a MANET with large address space.
In US Publication No. US20040174904A1 for a “Method of allocating IP address and detecting duplication of IP address in an ad-hoc network environment”, each host maintains a history table and a DAD table. The history table of a host stores the address history information of the host. The DAD table stores all neighbor address information. An ‘HELLO’ message is sent periodically between neighbors to update DAD tables. When a host needs an address, it sends a request message to its neighbors. If a neighbor finds such address in its DAD table, it will send a response message with an available message to the host, whereas other neighbors finding no such addresses in their DAD tables keep silence. If the host receives a response message from its neighbors, it sends a request message with such address for duplicate detection again. The process of duplicate detection will continue until no response message is received for N times. Such a method does not involve a broadcast in the whole network. However, ‘HELLO’ messages between neighbors are always sent periodically. This still cause lots of signal overhead in the network.